// 归并排序 时间复杂度：平均 O(nlogn) 最差 O(nlogn) 稳定 n大时较好
/**
 *
 * @param arr{Array}
 * @param left{number}
 * @param right{number}
 * @param temp{Array}
 */
function mergeSort (arr, left, right, temp) {
    if (left < right) {
        let mid = ~~((left + right) / 2)
        // 向左递归分解
        mergeSort(arr, left, mid, temp)
        // 向右递归分解
        mergeSort(arr, mid + 1, right, temp)
        // 合并
        merge(arr, left, mid, right, temp)
    }
}

/**
 * 合并方法
 * @param arr{Array}
 * @param left{number}
 * @param mid{number}
 * @param right{number}
 * @param temp{Array}
 */
function merge (arr, left, mid, right, temp) {
    let i = left // 左边有序序列索引
    let j = mid + 1 // 右边有序序列索引
    let t = 0  // 指向temp的索引
    // 1.把左右两边的有序数据按照规则填充到temp数组
    while (i <= mid && j <= right) {
        // 如果左边的有序序列的当前元素小于等于右边有序序列的当前元素
        // 将左边的的当前元素 填充到temp数组 然后t++ i++
        if (arr[i] <= arr[j]) {
            temp[t] = arr[i]
            t++
            i++
        } else { // 反之将右边的的当前元素 填充到temp数组 然后t++ j++
            temp[t] = arr[j]
            t++
            j++
        }
    }
    // 2.把剩余数据的一边依次填充到temp数组
    while (i <= mid) { // 说明左边还有剩余元素
        temp[t] = arr[i]
        t++
        i++
    }
    while (j <= right) { // 说明右边还有剩余元素
        temp[t] = arr[j]
        t++
        j++
    }
    // 3.将temp数组拷贝到arr
    t = 0
    let tempLeft = left
    while (tempLeft <= right) {
        arr[tempLeft] = temp[t]
        t++
        tempLeft++
    }
}

function main () {
    let arr = [8, 4, 5, 7, 1, 3, 6, 2]
    let temp = []
    mergeSort(arr, 0, arr.length - 1, temp)
    console.log(arr)
}

main()
